//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 
//
// 示例 1: 
//
// 输入: "abcabcbb"
//输出: 3 
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 
//
// 示例 2: 
//
// 输入: "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
// 
//
// 示例 3: 
//
// 输入: "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
// 
// Related Topics 哈希表 双指针 字符串 Sliding Window 
// 👍 4256 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.HashSet;

// Java3: 无重复字符的最长子串
public class Q3LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new Q3LongestSubstringWithoutRepeatingCharacters().new Solution();
        System.out.println(solution.better("ababe"));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            return better(s);
        }

        private int my(String s) {
            if (s == null || s.equals("") || s.length() <= 0) return 0;
            if (s.length() == 1) return 1;

            int re = 0;
            char[] chars = s.toCharArray();

            HashSet<Character> set = new HashSet<>();
            for (int i=0; i<chars.length; i++) {
                set.add(chars[i]);
                for (int r=i+1; r<chars.length; r++) {
                    if (!set.add(chars[r])) {
                        break;
                    }
                }
                int len = set.size();
                if (re == 0 || re < len) {
                    re = len;
                }
                set.clear();
            }
            return re;
        }

        /**
         * i遍历字符串，每次以 i 值记录，
         * 不回溯 i 值，用flag记录遍历过程找到的重复的字符的位置。
         * 如果遇到重复字符，i-flag 即为子串长度，
         * 此时flag重新定位到子串中重复字符的位置，i 继续往后遍历。
         */
        private int better(String s) {
            int rs = 0;
            int pre = 0;
            char[] cs = s.toCharArray();
            HashMap<Character, Integer> map = new HashMap<>();
            for (int i=0; i<cs.length; i++) {
                char c = cs[i];
                if (map.containsKey(c)) {
                    pre = Math.max(pre, map.get(c) + 1);
                }
                int len = i - pre + 1;
                if (rs < len) rs = len;
                map.put(c, i);
            }
            return rs;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}

